package club.xiaojiawei.binarytree;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @author 肖嘉威
 * @version 1.0
 * @date 5/15/22 2:45 PM
 * @question 513. 找树左下角的值
 * @description 给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。
 * 假设二叉树中至少有一个节点。
 */
public class FindBottomLeftValue513 {

    public static void main(String[] args) {
        TreeNode root = new TreeNode(2);
        root.left = new TreeNode(1);
        root.right = new TreeNode(3);
        int result = findBottomLeftValue2(root);
        System.out.println(result);
    }

    /**
     * BFS+队列
     * @param root
     * @return
     */
    public static int findBottomLeftValue(TreeNode root) {
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int result = root.val, size;
        while ((size = queue.size()) > 0){
            for (int i = 0; i < size; i++) {
                TreeNode current = queue.pop();
                if (i == 0){
                    result = current.val;
                }
                if (current.left != null){
                    queue.add(current.left);
                }
                if (current.right != null){
                    queue.add(current.right);
                }
            }
        }
        return result;
    }

    /**
     * 民间-BFS+队列
     * @param root
     * @return
     */
    public static int findBottomLeftValue3(TreeNode root) {
        Deque<TreeNode> deque = new LinkedList<>();
        deque.offer(root);
        TreeNode poll = null;
        while (!deque.isEmpty()){
            poll = deque.poll();
            if (poll.right != null){
                deque.offer(poll.right);
            }
            if (poll.left != null){
                deque.offer(poll.left);
            }
        }
        return poll.val;
    }

    /**
     * DFS+递归
     * @param root
     * @return
     */
    public static int findBottomLeftValue2(TreeNode root) {
        int[] result = {-1, 0};
        recursion(root, 0, result);
        return result[1];
    }

    public static void recursion(TreeNode node, int depth, int[] result){
        if (node == null){
            return;
        }
        if (depth > result[0]){
            result[0] = depth;
            result[1] = node.val;
        }
        recursion(node.left, ++depth, result);
        recursion(node.right, depth, result);
    }

    static class TreeNode{

        private int val;

        private TreeNode left;

        private TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }

        public int getVal() {
            return val;
        }

        public void setVal(int val) {
            this.val = val;
        }

        public TreeNode getLeft() {
            return left;
        }

        public void setLeft(TreeNode left) {
            this.left = left;
        }

        public TreeNode getRight() {
            return right;
        }

        public void setRight(TreeNode right) {
            this.right = right;
        }
    }
}
